package com.sheng.leetcode.year2023.month07.day31;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/07/31
 * <p>
 * 876. 链表的中间结点<p>
 * <p>
 * 给你单链表的头结点 head ，请你找出并返回链表的中间结点。<p>
 * 如果有两个中间结点，则返回第二个中间结点。<p>
 * <p>
 * 示例 1：<p>
 * 输入：head = [1,2,3,4,5]<p>
 * 输出：[3,4,5]<p>
 * 解释：链表只有一个中间结点，值为 3 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：head = [1,2,3,4,5,6]<p>
 * 输出：[4,5,6]<p>
 * 解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。<p>
 * <p>
 * 提示：<p>
 * 链表的结点数范围是 [1, 100]<p>
 * 1 <= Node.val <= 100<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/middle-of-the-linked-list">876. 链表的中间结点</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0876 {

    @Test
    public void test01() {
//        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6))))));
        ListNode listNode = new Solution876().middleNode(head);
        System.out.println(listNode);
    }
}

class Solution876 {
    public ListNode middleNode(ListNode head) {
        // 利用快慢指针，快指针每次走两步，慢指针每次走一步，所以快指针走的距离为慢指针的两倍，故当快指针遍历到链表末尾时，慢指针指向记为中间节点
        ListNode pointer1 = head, pointer2 = head;
        while (pointer1 != null && pointer1.next != null) {
            pointer2 = pointer2.next;
            pointer1 = pointer1.next.next;
        }
        return pointer2;
    }
}

/*
  Definition for singly-linked list.
  public class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
 */
